/*
 * @lc app=leetcode.cn id=300 lang=swift
 *
 * [300] 最长上升子序列
 */

// @lc code=start
class Solution300 {
    // 非常经典
    // 递推表达式：每次向后推进一个，都需要利用前面的所有dp看推进的一个是否能构成最长的
    func lengthOfLIS(_ nums: [Int]) -> Int {
        var dp = Array(repeating: 1, count: nums.count)
        var result = 0
        for i in 0..<nums.count {
            for j in 0..<i {
                if nums[i] > nums[j] {
                    dp[i] = max(dp[i], dp[j] + 1)
                }
            }
            result = max(result, dp[i])
        }
        return result
    }
    static func test() {
        let nums1 = [10, 9, 2, 5, 3, 7, 101, 18]
        let nums2 = [0,1,0,3,2,3]
        let nums3 = [7,7,7,7,7,7,7]
        let num4 = [4,10,4,3,8,9]
        let num5 = [1,3,6,7,9,4,10,5,6]
        let result = Solution300().lengthOfLIS(num5)
        print(result)
    }
}
// @lc code=end

